#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 150005;
int n, m, Q, A[MAXN]; int64_t X[MAXN];
int64_t query(int k){
  int64_t res = 0;
  deque<int> Id;
  for(int i = 0, j = 0; i <= k; i++){
    for(; j <= k && j <= i + m; j++) if(X[j] < 0) Id.push_back(j);
    while(X[i] && !Id.empty()){
      int64_t x = min(X[i], -X[Id.front()]); X[i] -= x, res += x;
      if(!(X[Id.front()] += x)) Id.pop_front();
    } if(res += X[i], i + m <= k) X[i + m] += X[i];
  } return res;
}
int main(){
  freopen("clear.in", "r", stdin);
  freopen("clear.out", "w", stdout);
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> Q;
  for(int i = 1; i <= n; i++) cin >> A[i];
  while(Q--){
    int l, r; cin >> l >> r;
    X[0] = A[l];
    for(int i = l + 1; i <= r; i++) X[i - l] = A[i] - A[i - 1];
    cout << query(r - l) << '\n';
  }
  return 0;
}
